#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
#define MAXN 4005
#define LL long long

const LL INF = 1000000000000000000LL;

int T, Cas = 1, N;

struct Node {
	LL x, y;
} p[MAXN];

// LL dp[MAXN][MAXN];

LL pool_sum[MAXN], tennis_sum[MAXN], tennis_order[MAXN], tennis_reverse[MAXN], pool_order[MAXN], pool_reverse[MAXN], len_order[MAXN], len_reverse[MAXN];

LL dp1[2][MAXN], dp2[2][MAXN];

void work() {
	printf("Case #%d: ", Cas ++);
	scanf("%d", &N);
	memset(tennis_order, 0, sizeof(tennis_order));
	memset(tennis_reverse, 0, sizeof(tennis_reverse));
	memset(pool_order, 0, sizeof(pool_order));
	memset(pool_reverse, 0, sizeof(pool_reverse));
	pool_sum[0] = 0LL;
	tennis_sum[0] = 0LL;
	for (int i = 1; i <= N; i ++) {
		scanf("%lld %lld", &p[i].x, &p[i].y);
		tennis_sum[i] = tennis_sum[i - 1] + p[i].x;
		pool_sum[i] = pool_sum[i - 1] + p[i].y;
	}
	tennis_order[0] = pool_order[0] = tennis_reverse[N + 1] = pool_reverse[N + 1] = 0LL;
	for (int i = 1; i <= N; i ++) {
		tennis_order[i] = tennis_order[i - 1] + i * p[i].x;
		pool_order[i] = pool_order[i - 1] + i * p[i].y;
		len_order[i] = i;
	}
	for (int i = N, j = 1; i >= 1; i --, j ++) {
		tennis_reverse[i] = tennis_reverse[i + 1] + j * p[i].x;
		pool_reverse[i] = pool_reverse[i + 1] + j * p[i].y;
		len_reverse[i] = j;
	}
	/*  for (int i = 0; i <= N; i ++) {
		for (int j = 0; j <= N; j ++) {
		dp[i][j] = INF;
		}
		}*/
	//  dp[0][0] = 0LL;
	int pre = 0, now = 1;
	fill(dp1[pre], dp1[pre] + N + 1, INF);
	fill(dp2[pre], dp2[pre] + N + 1, INF);
	dp1[pre][0] = 0LL; // [i, 0 -> i]
	dp2[pre][0] = 0LL; // [0 -> i, i];
	for (int i = 0; i < N; i ++) {
		fill(dp1[now], dp1[now] + N + 1, INF);
		fill(dp2[now], dp2[now] + N + 1, INF);
		for (int j = 0; j <= i; j ++) {
			int len, from, to;
			LL cost = 0LL;
			//        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
			dp1[now][j] = min(dp1[now][j], dp1[pre][j]);
			cost = 0LL;
			if (j) {
				len = i + 1 - j + 1;
				if (len & 1) {
					from = j, to = j + len / 2;
					cost = cost + (pool_order[to] - pool_order[from - 1]) - (pool_sum[to] - pool_sum[from - 1]) * len_order[from];
					from = j + len / 2 + 1, to = i + 1;
					cost = cost + (pool_reverse[from] - pool_reverse[to + 1]) - (pool_sum[to] - pool_sum[from - 1]) * len_reverse[to];
				} else {
					from = j, to = j + len / 2 - 1;
					cost = cost + (pool_order[to] - pool_order[from - 1]) - (pool_sum[to] - pool_sum[from - 1]) * len_order[from];
					from = j + len / 2, to = i + 1;
					cost = cost + (pool_reverse[from] - pool_reverse[to + 1]) - (pool_sum[to] - pool_sum[from - 1]) * len_reverse[to];
				}
			} else {
				from = 1, to = i + 1;
				cost = cost + (pool_reverse[from] - pool_reverse[to + 1]) - (pool_sum[to] - pool_sum[from - 1]) * len_reverse[to];
			}
			//          dp[i][i + 1] = min(dp[i][i + 1], dp[i][j] + cost);
			dp2[now][i] = min(dp2[now][i], dp1[pre][j] + cost);

			//            dp[j][i + 1] = min(dp[j][i + 1], dp[j][i]);
			dp2[now][j] = min(dp2[now][j], dp2[pre][j]);
			cost = 0LL;
			if (j) {
				len = i + 1 - j + 1;
				if (len & 1) {
					from = j, to = j + len / 2;
					cost = cost + (tennis_order[to] - tennis_order[from - 1]) - (tennis_sum[to] - tennis_sum[from - 1]) * len_order[from];
					from = j + len / 2 + 1, to = i + 1;
					cost = cost + (tennis_reverse[from] - tennis_reverse[to + 1]) - (tennis_sum[to] - tennis_sum[from - 1]) * len_reverse[to];
				} else {
					from = j, to = j + len / 2 - 1;
					cost = cost + (tennis_order[to] - tennis_order[from - 1] - (tennis_sum[to] - tennis_sum[from - 1]) * len_order[from]);
					from = j + len / 2, to = i + 1;
					cost = cost + (tennis_reverse[from] - tennis_reverse[to + 1]) - (tennis_sum[to] - tennis_sum[from - 1]) * len_reverse[to];
				}
			} else {
				from = 1, to = i + 1;
				cost = cost + (tennis_reverse[from] - tennis_reverse[to + 1]) - (tennis_sum[to] - tennis_sum[from - 1]) * len_reverse[to];
			}
			//        dp[i + 1][i] = min(dp[i + 1][i], dp[j][i] + cost);
			dp1[now][i] = min(dp1[now][i], dp2[pre][j] + cost);
		}
		swap(now, pre);
	}
	LL res = INF;
	for (int i = 1; i < N; i ++) {
		LL cost = 0LL;
		int from, to;
		from = i, to = N;
		cost = cost + (tennis_order[to] - tennis_order[from - 1]) - (tennis_sum[to] - tennis_sum[from - 1]) * len_order[from];
		res = min(res, dp2[pre][i] + cost);
		from = i, to = N, cost = 0LL;
		cost = cost + (pool_order[to] - pool_order[from - 1]) - (pool_sum[to] - pool_sum[from - 1]) * len_order[from];
		res = min(res, dp1[pre][i] + cost);
	}
	cout << res << endl;
}

int main()
{
	scanf("%d", &T);
	while (T --) {
		work();
	}
	return 0;
}

